/*
 * @Author: liusheng
 * @Date: 2022-05-04 17:14:55
 * @LastEditors: liusheng
 * @LastEditTime: 2022-05-05 20:40:52
 * @Description: contains-duplicate-iii
 * email:liusheng613@126.com
 * Copyright (c) 2022 by liusheng/liusheng, All Rights Reserved. 
 * 
 剑指 Offer II 057. 值和下标之差都在给定的范围内
给你一个整数数组 nums 和两个整数 k 和 t 。请你判断是否存在 两个不同下标 i 和 j，使得 abs(nums[i] - nums[j]) <= t ，同时又满足 abs(i - j) <= k 。

如果存在则返回 true，不存在返回 false。

 

示例 1：

输入：nums = [1,2,3,1], k = 3, t = 0
输出：true
示例 2：

输入：nums = [1,0,1,1], k = 1, t = 2
输出：true
示例 3：

输入：nums = [1,5,9,1,5,9], k = 2, t = 3
输出：false
 

提示：

0 <= nums.length <= 2 * 104
-231 <= nums[i] <= 231 - 1
0 <= k <= 104
0 <= t <= 231 - 1
 

注意：本题与主站 220 题相同： https://leetcode-cn.com/problems/contains-duplicate-iii/

通过次数7,989 提交次数22,917
 */

#include "header.h"

/*
time:O(n^2)
timeout solution
*/
class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        int n = nums.size();
        for (int i = 0; i < n; ++i)
        {
            for (int j = i + 1; j < n && j <= i + k; ++j)
            {
                if (abs((long)nums[j] - nums[i]) <= t)
                {
                    return true;
                }
            }
        }

        return false;
    }
};

/*
slide widown solution
keep window width is k,if any element in the slide window is [x-t,x + t],it will satisfy the 
solution
*/
class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) 
    {
        int n = nums.size();
        //maintance at most k sorted elements
        multiset<long> sortedNums;
        int startPos = 0;
        
        for (int i = 0; i < n; ++i)
        {   
            // printf("sortedNum size:%d\n",sortedNums.size());
            auto itlow = sortedNums.lower_bound(((long)nums[i] - t));
            auto itup = sortedNums.upper_bound(((long)nums[i] + t));
            //has value in range [nums[i] - t,nums[i] + t]
            if (itlow != itup)
            {
                return true;
            }

            sortedNums.insert(nums[i]);
            if (sortedNums.size() > k)
            {
                sortedNums.erase(nums[i-k]);
            }
        }

        return false;
    }
};

/*
same as above,use set not multiset,because there are no duplicate values
if has duplicated value,it will return true
*/
class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) {
        int n = nums.size();
        set<long> atmostKNumsBefore;
        for (int i = 0; i < n; ++i)
        {
            auto itlow = atmostKNumsBefore.lower_bound((long)nums[i] - t);
            auto itup = atmostKNumsBefore.upper_bound((long)nums[i] + t);
            
            //nums[i]'s prev k number has the value in
            // [nums[i] - t,nums[i] + t]
            if (itlow != itup)
            {
                return true;
            }
            
            atmostKNumsBefore.insert(nums[i]);
            if (i >= k)
            {
                atmostKNumsBefore.erase(nums[i-k]);
            }
        }
        
        return false;
    }
};

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector<int>& nums, int k, int t) 
    {
        int n = nums.size();
        long bucketSize = (long)t + 1;
        unordered_map<long,long> buckets;//store bucketid,remapNum
        for (int i = 0; i < n; ++i)
        {
            long remappintgVal = (long)nums[i] - INT_MIN;
            long bucketId = remappintgVal / bucketSize;
            if (buckets.count(bucketId))
            {
                return true;
            }

            if (buckets.count(bucketId - 1) && (long)nums[i] - buckets[bucketId - 1] <= t)
            {
                return true;
            }

            if (buckets.count(bucketId + 1) && (long)buckets[bucketId + 1] - nums[i] <= t)
            {
                return true;
            }

            buckets[bucketId] = nums[i];
            // Making sure only K buckets exists in map.
            if (i >= k)
            {
                long lastBucketId = ((long)nums[i-k] - INT_MIN) / bucketSize;
                buckets.erase(lastBucketId);
            }
        }
        return false;
    }
};